国防科技大学 编译原理 第12讲 语法分析——自下而上分析3

距离上次更新已经 1534 天了，文章内容可能已经过时。

课程主页：

https://www.icourse163.org/course/NUDT-1003101005?tid=1460976445

这次回顾第12讲：语法分析——自下而上分析3。

第12讲$LR(0)$分析表的构造

$LR$分析法回顾

$LR$分析法

工作框架：

规范归约

• 定义：假定$\alpha$是文法$G$的一个句子，我们称序列${\alpha }_n,{\alpha }_{n-1},\dots ,{\alpha }_0$是$\alpha$的一个规范归约，如果此序列满足：
  • ${\alpha }_n=\alpha$
  • ${\alpha }_0$为文法的开始符号，即${\alpha }_0=S$
  • 对任何$i$，$0\le i\le n$，${\alpha }_{i-1}$是从${\alpha }_i$经把句柄替换成为相应产生式左部符号而得到的

内容回顾

短语、直接短语和句柄

• 定义：令$G$是一个文法，$S$是文法的开始符号，假定$\alpha \beta \delta$是文法$G$的一个句型，如果有

  $$S\stackrel{\star }{\Rightarrow }\alpha A\delta \mathrm{且}A\stackrel{+}{\Rightarrow }\beta$$

  则称$\beta$是句型$\alpha \beta \delta$相对于非终结符$A$的短语。

• 如果有$A\Rightarrow \beta$，则称$\beta$是句型$\alpha \beta \delta$相对于规则$A\to b$的直接短语。

• 一个句型的最左直接短语称为该句型的句柄。

• 在一个句型对应的语法树中

  • 以某非终结符为根的两代以上的子树的所有末端结点从左到右排列就是相对于该非终结符的一个短语
  • 如果子树只有两代，则该短语就是直接短语
  • 最左两代子树末端就是句柄

规范句型

• 规范归约是最左归约

• 规范归约的逆过程就是最右推导

  $$S\Rightarrow aAcBe\Rightarrow aAcde\Rightarrow aAbcde\Rightarrow abbcde$$

• 最右推导也称为规范推导

• 由规范推导推出的句型称为规范句型

$LR$分析法

$LR$分析器的性质

• 栈内的符号串和扫描剩下的输入符号串构成了一个规范句型
• 一旦栈的顶部出现可归约串(句柄)，则进行归约

测试：规范归约过程中栈内符号串

对于句子，在规范归约过程中，栈内的符号串和扫描剩下的输入符号串构成了一个规范句型，下面哪种格局不会出现：

答案是D。

活前缀

字的前缀、活前缀

• 字的前缀：是指字的任意首部，如字$abc$的前缀有$\epsilon ,a,ab,abc$
• 活前缀：是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。即，对于规范句型$\alpha \beta \delta$，$\beta$为句柄，如果$\alpha \beta =u_1{u}_2\dots u_r$，则符号串$u_1{u}_2\dots u_i(1\le i\le r)$是$\alpha \beta \delta$的活前缀。($\delta$必为终结符串)
• 规范归约过程中，保证分析栈中总是活前缀，就说明分析采取的移进/归约动作是正确的

识别活前缀

• 能否判断一个符号串是不是活前缀？
• 对于一个文法$G$, 可以构造一个DFA，它能识别$G$的所有活前缀。

构造识别活前缀的DFA

文法的拓广

• 将文法$G(S)$拓广为$G\prime (S\prime )$
  • 构造文法$G\prime$，它包含了整个$G$，并引进不出现在$G$中的非终结符$S\prime$、以及产生式$S\prime \to S$，$S\prime$是$G\prime$的开始符号
  • 称$G\prime$是$G$的拓广文法

$LR(0)$项目

• $LR(0)$项目
  • 在每个产生式的右部添加一个圆点
  • 表示我们在分析过程中看到了产生式多大部分
• $A\to XYZ$有四个项目
  • $A\to •XYZ,A\to X•YZ,A\to XY•Z,A\to XYZ•$
• $A\to \alpha •$称为”归约项目”
• 归约项目$S\prime \to \alpha •$称为”接受项目”
• $A\to \alpha •a\beta (a\in V_T)$称为”移进项目”
• $A\to \alpha •B\beta (B\in V_N)$称为”待约项目”

示例

考虑文法$G\left(S^{\prime }\right)$：

$$\begin{array}{rl}{\mathrm{S}}^{\prime }& \to \mathrm{E}\\ \mathrm{E}& \to \mathrm{aA}\mid \mathrm{bB}\\ \mathrm{A}& \to \mathrm{cA}\mid \mathrm{d}\\ \mathrm{B}& \to \mathrm{cB}\mid \mathrm{d}\end{array}$$

该文法的项目有：

构造识别文法所有活前缀的DFA

• 构造识别文法所有活前缀的NFA
  • 若状态$i$为$X\to X_1\dots X_{i-1}•X_i\dots X_n$，状态$j$为$X\to X_1\dots X_{i-1}{X}_i•X_{i+1}\dots X_n$，则从状态$i$画一条标志为$X_i$的有向边到状态$j$；
  • 若状态$i$为$X\to \alpha •A\beta$，$A$为非终结符，则从状态$i$画一条$\epsilon$边到所有状态$A\to •\gamma$
• 把识别文法所有活前缀的NFA确定化

识别活前缀的NFA

识别活前缀的DFA

将NFA确定化之后可得：

$LR(0)$项目集规范族

构成识别一个文法活前缀的DFA的项目集(状态)的全体称为文法的$LR(0)$项目集规范族。

通过计算项目集规范族构造识别活前缀的DFA

有效项目

• 项目$A\to {\beta }_1•{\beta }_2$对活前缀$\alpha {\beta }_1$是有效的，其条件是存在规范推导$${\mathrm{S}}^{\prime }{\stackrel{\star }{\Rightarrow }}_R\alpha A\omega {\Rightarrow }_R\alpha {\beta }_1{\beta }_2\omega$$
• 在任何时候，分析栈中的活前缀$X_1{X}_2\dots X_m$的有效项目集正是从识别活前缀的DFA的初态出发，读出$X_1{X}_2\dots X_m$后到达的那个项目集(状态)。

有效项目的性质

• 若项目$A\to \alpha •B\beta$对活前缀$\eta =\delta \alpha$是有效的且$B\to \gamma$是一个产生式，则项目$B\to •\gamma$对$\eta =\delta \alpha$也是有效的。

证明：

若项目$A\to \alpha •B\beta$对活前缀$\eta =\delta \alpha$是有效的，则有

$${\mathrm{S}}^{\prime }{\stackrel{\star }{\Rightarrow }}_R\delta A\omega {\Rightarrow }_R\delta \alpha B\beta \omega$$

设

$$\beta \omega {\stackrel{\star }{\Rightarrow }}_R\phi \omega$$

那么

$${\mathrm{S}}^{\prime }{\Rightarrow }_R\delta A\omega {\Rightarrow }_R\delta \alpha B\beta \omega {\stackrel{\ast }{\Rightarrow }}_R\delta \alpha B\phi \omega {\Rightarrow }_R\delta \alpha \gamma \phi \omega$$

所以，$B\to •\gamma$对$\eta =\delta \alpha$也是有效的

$LR(0)$项目集规范族的构造

• 将文法$G(S)$拓广为$G\prime (S\prime )$
  • 构造文法$G\prime$，它包含了整个$G$，并引进不出现在$G$中的非终结符$S\prime$、以及产生式$S\prime \to S$，$S\prime$是$G\prime$的开始符号
  • $G\prime$唯一的“接受”态：仅含项目$S\prime \to S•$的状态

状态转换函数

• 为了识别活前缀，我们定义一个状态转换函数$\mathrm{GO}$是一个状态转换函数。$I$是一个项目集，$X$是一个文法符号。函数值$\mathrm{GO}(I,X)$定义为：

  $$\mathrm{GO}(I,X)＝\mathrm{CLOSURE}(J)$$

  其中

  $$\mathrm{J}=\{\text{ 任何形如 }A\to \alpha X\cdot \beta \text{ 的项目| }A\to \alpha \cdot X\beta \text{ 属于}I\}$$

• 直观上说，若$I$是对某个活前缀$\gamma$有效的项目集，那么，$\mathrm{GO}(I,X)$便是对$\gamma X$有效的项目集。

示例：项目集的转移函数计算

给定文法$G\left(S^{\prime }\right)$：

$$\begin{array}{rl}{\mathrm{S}}^{\prime }& \to \mathrm{E}\\ \mathrm{E}& \to \mathrm{aA}\mid \mathrm{bB}\\ \mathrm{A}& \to \mathrm{cA}\mid \mathrm{d}\\ \mathrm{B}& \to \mathrm{cB}\mid \mathrm{d}\end{array}$$

考虑

$$I_0=\{S^{\prime }\to •E,E\to •aA,E\to •bB\}$$

计算$\mathrm{GO}$可得：

$$\begin{array}{rl}\mathrm{GO}(I_0,E)& =\mathrm{closure}(J)\\ & =\mathrm{closure}(\{S^{\prime }\to E•\})\\ & =\{S^{\prime }\to E•\}\\ & =I_1\\ \mathrm{GO}(I_0,a)& =\mathrm{closure}(J)\\ & =\mathrm{closure}(\{E\to a•A\})\\ & =\{E\to a•A,A\to •cA,A\to •d\}\\ & =I_2\\ \mathrm{GO}(I_0,b)& =\mathrm{closure}(J)\\ & =\mathrm{closure}(\{E\to b•B\})\\ & =\{E\to b•B,B\to •cB,B\to •d\}\\ & =I_3\end{array}$$

LR(0)项目集规范族的构造算法

• $\text{PROCEDURE ITEMSETS(G′)}$；
• $\text{BEGIN}$
  • $\text{C:={CLOSURE({S′→•S})} }$；
  • $\text{REPEAT}$
    • $\text{FOR C}$中每个项目集$\mathrm{I}$和$G\prime$的每个符号$\text{X DO}$
      • $\text{IF GO(I, X)}$非空且不属于$\text{C THEN}$
        • 把$\text{GO(I, X)}$放入$\mathrm{C}$族中;
  • $\text{UNTIL C}$不再增大
• $\mathrm{END}$

两种构造识别活前缀的DFA的方法

1. 项目 → NFA → DFA
2. Closure → GO → DFA

构造$LR(0)$分析表的算法

$LR(0)$分析表的构造

• 假若一个文法$G$的拓广文法$G\prime$的活前缀识别自动机中的每个状态(项目集)不存在下述情况

  • 既含移进项目又含归约项目；
  • 含有多个归约项目

  则称$G$是一个$LR(0)$文法。

构造$LR(0)$分析表的算法

• 令每个项目集$I_k$的下标$k$作为分析器的状态，包含项目$S\prime \to •S$的集合$I_k$的下标$k$为分析器的初态。
• 构造$LR(0)$分析表的$\text{ACTION}$和$\text{GOTO}$子表。

$LR(0)$分析表的ACTION和GOTO子表构造

1. 若项目$A\to \alpha •a\beta$属于$I_k$且$\mathrm{GO}(I_k,a)＝I_j$，$a$为终结符，则置$\mathrm{ACTION}[k,a]$为“$s_j$”。
2. 若项目$A\to \alpha •$属于$I_k$，那么，对任何终结符$a$(或结束符$\mathrm{♯}$)，置$\text{ACTION}[k,a]$为“$r_j$”(假定产生式$A\to \alpha$是文法$G\prime$的第$j$个产生式)。
3. 若项目$S\prime \to S•$属于$I_k$，则置$\text{ACTION}[k,\mathrm{♯}]$为“$\text{acc}$”。
4. 若$\mathrm{GO}(I_k,A)＝I_j$，$A$为非终结符，则置$\mathrm{GOTO}[k,A]=j$。
5. 分析表中凡不能用规则1至4填入信息的空白格均置上“报错标志”。

示例：$LR(0)$分析表的构造

$LR(0)$分析示例

按照$LR(0)$分析表对$bcd$进行分析：

小结

• 规范归约过程中，只要保证分析栈中总是活前缀，就说明分析采取的移进/归约动作是正确的
• 哪些字符串是活前缀?能不能构造一个DFA来识别活前缀?
• 项目->NFA ->DFA
• Closure->GO->DFA
• 将识别活前缀的DFA转换成LR分析表